package main.old.new_2023.last.month_6;

/**
 * @Description:
 * //TODO 2. 两数相加
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * //todo 27. 移除元素
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 * //todo 35. 搜索插入位置
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * 请必须使用时间复杂度为 O(log n) 的算法。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/

public class Solution0605_2 {
    //两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 创建一个虚拟头节点【不要动他】
        ListNode vir = new ListNode();
        // 创建一个指针指向头节点【动他】
        ListNode pre = vir;
        // 定义一个变量表示进位
        int cur = 0;
        // 遍历两个链表，直到都为空
        while (l1!= null || l2!= null){
            // 取出两个链表的当前值，如果为空则为0【① 取出加数 被加数】
            int l1Value = l1 == null ? 0 : l1.val;
            int l2Value = l2 == null ? 0 : l2.val;
            // 计算两个值的和，加上进位【② 先求和：加数+被加数+进位】
            int sumValue = l1Value + l2Value+cur;
            // 更新进位，如果和大于等于10，则进位为1，否则为0【③ 再更新进位carry，只有两个取值1,0】
            cur = sumValue >= 10 ? 1:0;
            // 创建一个新的节点，存储和的个位数【④ 最后节点存入结果（链表）sum的个位】
            pre.next = new ListNode(sumValue % 10);
            //            =========    循环指针更新    =============
            // 移动指针到下一个节点
            pre = pre.next;
            // 如果链表不为空，则移动到下一个节点
            if (l1 != null){
                l1 = l1.next;
            }
            if (l2 != null){
                l2 = l2.next;
            }
        }
        // 如果最后还有进位，则在末尾添加一个节点【把多的那个进位 存上】
        if (cur == 1){
            pre.next = new ListNode(cur);
        }
        // 返回虚拟头节点的下一个节点，即真正的头节点
        return vir.next;
    }

    //移除元素
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }

    //搜索插入位置
    public int searchInsert(int[] nums, int target) {
        int max = nums.length;
        for (int i =0;i<nums.length;i++){
            int min = nums[i];
            if (target == min){
                return i;
            }else if (target < min){
                return i;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {1,3,5,6};
        Solution0605_2 solu = new Solution0605_2();
        int i = solu.searchInsert(nums, 7);
        System.out.println(i);
    }

public class ListNode {
     int val;
      ListNode next;
      ListNode() {}
     ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

}
